public class Test24 {
    public static boolean verifySequenceOfBST(int[] sequence){
        if (sequence == null || sequence.length == 0) return false;
        return Bfs(sequence,0,sequence.length-1);

    }
    public static boolean Bfs(int[] sequence,int start,int end){
        if (start >= end) return true;
        int index = start;
        //这段为寻找左子树，左子树的值都小于根结点
        while(index <end -1 && sequence[index] < sequence[end]){
            index ++;
        }
        int right = index; //右子树的第一个点
        //这段可以看作右子树，右子树的点都大于根结点
        while (index < end-1 &&sequence[index] > sequence[end]){
            index ++;
        }
        if (index != end-1) return false;
        return Bfs(sequence,start,right-1) && Bfs(sequence,right,end-1);

    }

    public static void main(String[] args) {
        int[] data = {4, 8, 6, 12, 16, 14, 10};
        //           10
        //         /   \
        //        6     14
        //       /\     /\
        //      4  8  12  16
        System.out.println(verifySequenceOfBST(data));
    }
}
